/**
 * 1579. 保证图可完全遍历
 * https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/
 */
public class Solutions_1579 {
    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{3, 1, 2}, {3, 2, 3}, {1, 1, 3}, {1, 2, 4},
                        {1, 1, 2}, {2, 3, 4}};  // output: 2

//        int n = 4;
//        int[][] edges = {{3, 1, 2}, {3, 2, 3}, {1, 1, 4}, {2, 1, 4}};  // output: 0

//        int n = 4;
//        int[][] edges = {{3, 2, 3}, {1, 1, 2}, {2, 3, 4}};  // output: -1

        int result = maxNumEdgesToRemove(n, edges);
        System.out.println(result);
    }

    /**
     * 解题思路：并查集
     * 关键：
     * 贪心原则，若 1、2 之间有三条边，即类型 1、2、3 的边各一条
     * 那么仅保留类型 3 的边即可，则可以删除类型 1、2 的两条边，优先合并公共边
     */
    public static int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind_1579 ufA = new UnionFind_1579(n);
        UnionFind_1579 ufB = new UnionFind_1579(n);

        int ans = 0;
        // 首次遍历，对公共边进行合并
        for (int[] edge : edges) {
            if (edge[0] == 3) {
//                boolean flagA = ufA.union(edge[1], edge[2]);
//                boolean flagB = ufB.union(edge[1], edge[2]);
//                if (!flagA && !flagB) {
//                    // Alice 和 Bob 都不需要该边
//                    ans ++;
//                }
                if (!ufA.union(edge[1], edge[2])) {
                    ans ++;
                } else {
                    ufB.union(edge[1], edge[2]);
                }
                // 有一人不需要，即都不需要，因为首先遍历的是类型 3 的边
                // 即已经有其他的类型为 3 的边，连接了节点 edge[1] 和 edge[2] 了，那么边 edge[0] 是可以删除的
                // 例：edges = {{3, 1, 2}, {3, 2, 3}, {3, 1, 3}}，那么 [3, 1, 3] 的边是可以删除的
            }
        }
        // 二次遍历，对各自的边进行合并，合并过程中判断是否需要该边
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                // 检查 Alice 是否需要这条边
                if (!ufA.union(edge[1], edge[2])) {
                    ans ++;
                }
            } else if (edge[0] == 2) {
                // 检查 Bob 是否需要这条边
                if (!ufB.union(edge[1], edge[2])) {
                    ans ++;
                }
            }
        }
        // Alice 和 Bob 都可以完成完全遍历时，返回可以删除的最大边数
        if (ufA.check() && ufB.check()) {
            return ans;
        }
        return -1;
    }
}

class UnionFind_1579 {
    int[] parent;

    UnionFind_1579(int len) {
        // 节点从 1 开始的，所以从索引 1 开始计数
        parent = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            // 合并前，每个人都是独立的，没有上级
            parent[i] = i;
        }
    }

    // 查找 x 的最终老大
    int find(int x) {
        // 迭代查找最上级
        while (parent[x] != x) {
            // 关键：查找过程中完成赋值（提高效率：2136ms => 10ms）
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    /**
     * 指定 x 的上级为 y
     * 找到 x 的最上级以及 y 的最上级
     */
    boolean union(int x, int y) {
        int xBoss = find(x);
        int yBoss = find(y);
        if (xBoss == yBoss) {
            // 已经合并（指定）过，那么本次不需要合并（指定）
            return false;
        }
        // 关键：使 y 的最上级成为 x 的最上级的上级
        parent[xBoss] = yBoss;
        return true;
    }

    // 检查是否可以连接全部的节点
    boolean check() {
        int cnt = 0;
        for (int i = 1; i < parent.length; i++) {
            // 若可以一次连接全部的节点，那么最终只有一个上级
            if (parent[i] == i) {
                cnt ++;
                if (cnt > 1) {
                    return false;
                }
            }
        }
        return cnt == 1;
    }
}
